//给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 
//
// 说明：每次只能向下或者向右移动一步。 
//
// 示例: 
//
// 输入:
//[
//  [1,3,1],
//  [1,5,1],
//  [4,2,1]
//]
//输出: 7
//解释: 因为路径 1→3→1→1→1 的总和最小。
// 
// Related Topics 数组 动态规划


package leetcode.editor.cn;


public class A64MinimumPathSum {
    public static void main(String[] args) {
        Solution solution = new A64MinimumPathSum().new Solution();
        System.out.println("佛祖保佑");
        System.out.println("\uD80C\uDC09\uD80C\uDC02\uD80C\uDC03\uD80C\uDC10");
        int[][] a = new int[][]{
                new int[]{1, 3, 1},
                new int[]{1, 5, 1},
                new int[]{4, 2, 1}
        };

        System.out.println(solution.minPathSum(a));

    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 厚颜无耻地把输入的空间拿来用了！！
     * 解答成功:
     * 执行耗时:2 ms,击败了98.25% 的Java用户
     * 内存消耗:42.1 MB,击败了37.88% 的Java用户
     */
    class Solution {
        public int minPathSum(int[][] grid) {
            int m = grid.length;
            int n = grid[0].length;
            for (int i = 1; i < n; i++) {
                grid[0][i] += grid[0][i - 1];
            }

            for (int i = 1; i < m; i++) {
                grid[i][0] += grid[i - 1][0];
                for (int j = 1; j < n; j++) {
                    grid[i][j] += Math.min(grid[i][j - 1], grid[i - 1][j]);
                }
            }

            return grid[m - 1][n - 1];
        }
    }


    /**
     * 解答成功:
     * 执行耗时:3 ms,击败了89.89% 的Java用户
     * 内存消耗:42.4 MB,击败了30.30% 的Java用户
     */
    class Solution1 {
        public int minPathSum(int[][] grid) {
            int m = grid.length;
            int n = grid[0].length;
            int[][] dp = new int[m][n];
            dp[0][0] = grid[0][0];
            for (int i = 1; i < n; i++) {
                dp[0][i] = dp[0][i - 1] + grid[0][i];
            }

            for (int i = 1; i < m; i++) {
                dp[i][0] = dp[i - 1][0] + grid[i][0];
                for (int j = 1; j < n; j++) {
                    dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
                }
            }

            return dp[m - 1][n - 1];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
